<!--
 * @Author: zengwj
 * @Date: 2021-11-15 14:22:03
 * @LastEditors: zengwj
 * @LastEditTime: 2021-11-15 18:32:45
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /**
      * @param {character[][]} board
      * @return {void} Do not return anything, modify board in-place instead.
    */
    var solveSudoku = function (board) {

      function backtracking() {
        for (let i = 0; i < board.length; i++) {
          for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] !== '.') continue
            for (let val = 1; val <= 9; val++) {
              if (isValid(i, j, `${val}`, board)) {
                board[i][j] = `${val}`
                if (backtracking()) {
                  return true
                }

                board[i][j] = `.`
              }
            }
            return false
          }
        }
        return true
      }
      function isValid(i, j, val, board) {
        //  同行判断
        if (board[i].includes(val)) {
          return false
        }
        // 同列判断
        const sameLine = board.some(item =>
          item[j] === val
        )
        if (sameLine) {
          return false
        }
        // 九宫格判断
        const qiugX = Math.ceil((j + 1) / 3) || 1
        const qiugY = Math.ceil((i + 1) / 3) || 1
        const qiugongArr = []
        board.forEach((item, index) => {
          if (index < qiugY * 3 && index >= (qiugY - 1) * 3) {
            board[index].forEach((i, x) => {
              if (x < qiugX * 3 && x >= (qiugX - 1) * 3) {
                qiugongArr.push(board[index][x])
              }
            })
          }
        })

        if (qiugongArr.includes(val)) {
          return false
        }
        return true
      }
      backtracking()
      return board
    };
    console.log(
      solveSudoku(
        [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
      )
    );

  </script>
</body>

</html>